As used herein, the term error control coding (ECC) is intended to encompass broadly any kind of coding that is employed to assist in any one or more of: identifying the presence of a data error, identifying where in an amount of data an error is, and correcting an error. ‘Error control coding’ should not be confused with the more limited term ‘error correction coding’, which is treated herein as a sub-set of error control coding.
In the fields of data storage and data transmission in particular, it is well known to apply ECC to protect source data before the data is transmitted over a channel to be stored to a data storage medium or transmitted over a transmission medium. The term ‘channel’ is intended herein to encompass broadly the means (for example, electronics, optics and any other kinds of data processing elements) by which, for example, data is written to or read from a physical storage medium, or transmitted over or received from a physical or wireless communications medium.
ECC typically takes the form of additional data (which is sometimes referred to as ‘redundant’ data, or simply ‘redundancy’), which is added to or combined with the source data upstream of the channel (that is, before the data is written or transmitted). The term ‘source data’ is intended herein to mean the data to which the ECC will be applied, and does not imply any particular point of origin, the term ‘protected data’ is intended to mean the source data after it has been protected by ECC, and the term ‘recovered data’ is intended to mean data that has been retrieved from a storage medium after storage or receipt by a
receiver after transmission. In many cases, but not always, source data and protected data are the same, except that the protected data is accompanied by ECC data when it is applied to a channel. In a perfect system in which no storage or transmission errors occur, it is expected that the recovered data should match the source data without the need to employ the ECC data. However, when in a practical system the recovered data does not match the source data (that is, data errors have occurred), different degrees of ECC can be used to detect the presence of errors, indicate where the errors are and correct the errors in the recovered data.
There are a large number of very well known ECC data protection techniques, including parity, checksums, hashing algorithms and Reed-Solomon codes, to name just a few. Commonly, in ECC parlance, a ‘distance’ is defined as a number of differences (for example, errors) between the source data and the recovered data. Further, the term ‘minimum distance’ may be used to indicate, for a given ECC technique, a degree of error detecting and/or correcting that can be achieved; also bearing in mind that some techniques such as Reed-Solomon coding permit, for a given minimum distance, a degree of the correctability to be exchanged with a degree of the detectability (and vice versa). The minimum distance can also be thought of as the power, level or degree of protection afforded by the ECC employed.
Typically, the greater the minimum distance is required to be, the higher the degree of redundancy will be. In other words, for a given number of symbols (for example, bits, bytes, characters or words), which need to be protected using ECC, an increased minimum distance implies more ECC and an attendant, higher redundancy. Accordingly, system designers are always mindful of the trade-off between how much redundancy can be tolerated (that is, how efficient a storage system is in terms of storage capacity and/or throughput or how efficient a transmission system is in terms of source data bandwidth) and how well protected the data is required to be (that is, how reliable the system is at recovering from storage or transmission errors).